﻿#define _CRT_SECURE_NO_WARNINGS 1
DP
21. 乘积最⼤⼦数组（medium）
22. 乘积为正数的最长子数组（medium）
23. 等差数列划分（medium）
24. 最长湍流子数组（medium）
25. 单词拆分（medium）


https ://leetcode.cn/problems/maximum-product-subarray/submissions/575898543/
```cpp
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //分为两种情况
        //当前元素i为正数，子数组长度为1为自身，或者长度大于1此时前面数组为以[i-1]为结尾的最大值*当前元素
        //当前元素i为负数，子数组长度为1为自身，或者长度大于1此时前面数组为以[i-1]为结尾的最小值*当前元素
        int n = nums.size();
        if (n == 1)
            return nums[0];
        vector<int> maxdp(n);
        vector<int> mindp(n);
        maxdp[0] = mindp[0] = nums[0];
        int ret = nums[0];//乘积最大子数组一定在maxdp表中
        for (int i = 1; i < n; i++)
        {
            if (nums[i] > 0)
            {
                maxdp[i] = max(nums[i], maxdp[i - 1] * nums[i]);
                mindp[i] = min(nums[i], mindp[i - 1] * nums[i]);
            }
            else
            {
                maxdp[i] = max(nums[i], mindp[i - 1] * nums[i]);
                mindp[i] = min(nums[i], maxdp[i - 1] * nums[i]);
            }
            ret = max(ret, maxdp[i]);//更新max
        }
        return ret;
    }
};
```


# 22. 乘积为正数的最长子数组（medium）
https ://leetcode.cn/problems/maximum-length-of-subarray-with-positive-product/submissions/575906680/
```cpp
class Solution {
public:
    //pdp表为以i位置为结尾的乘积为正数子数组的最大值
    //分为三种情况
    //当前元素i为正数，此时pdp[i]为pdp[i-1]+1//因为pdp[i-1]乘积一定是正的
    //当前元素i为负数，此时我们需要另一个dp表（以i位置为结尾的乘积为负数子数组的最大值），此时pdp[i]为ndp[i-1]+1)
    //当前元素为零时，乘积为0，长度也就为0，其实这个不需要处理，vector初始化时每个值默认为0
    int getMaxLen(vector<int>& nums) {
        int n = nums.size();
        vector<int> pdp(n + 1);//p代表positive number 正数
        vector<int> ndp(n + 1);//同理
        //初始化时，比较麻烦，我们需要分别讨论nums[0]>0,<0,=0的情况因此我们加一个虚拟结点，里面的值为0
        int ret = nums[0] > 0 ? 1 : 0;
        //感觉还是采取不添加虚拟结点的方式方便一些
        for (int i = 1; i < n + 1; i++)
        {
            if (nums[i - 1] > 0)//注意下标的映射关系
            {
                pdp[i] = pdp[i - 1] + 1;//虚拟结点为0时,nums[i-1]>0可以直接加1
                if (ndp[i - 1] != 0)//前面结点不能为0
                    ndp[i] = ndp[i - 1] + 1;//虚拟结点为0时，不能直接+1
            }
            else if (nums[i - 1] < 0)
            {
                if (ndp[i - 1] != 0)
                    pdp[i] = ndp[i - 1] + 1;

                ndp[i] = pdp[i - 1] + 1;
            }

            ret = max(ret, pdp[i]);//更新
        }
        return ret;
    }
};
```
# 23. 等差数列划分（medium）

https ://leetcode.cn/problems/arithmetic-slices/submissions/575909388/
```cpp
class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        //包含i位置的等差数列数组的最大个数
        int n = nums.size();
        vector<int> dp(n);
        //如何将i位置加入到等差数列数组中满足
        //满足nums[i]-nums[i-1]==nums[i-1]-nums[i-2]即可加入
        int ret = 0;
        for (int i = 2; i < n; i++)
        {
            if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2])
                dp[i] = dp[i - 1] + 1;

            ret += dp[i];
        }
        return ret;
    }
};
```

# 24. 最长湍流子数组（medium）
https ://leetcode.cn/problems/longest-turbulent-subarray/submissions/575912017/
```cpp
class Solution {
public:
    int maxTurbulenceSize(vector<int>& arr) {
        //理解题目，其实就是波形图，就是一上一下一上一下，或者一下一上
        //不过当数组中只有一个元素时，可以对应余弦和正弦也是湍流子数组,因此初始化dp表时我们可以全初始化为1
        //这样前一个元素和后一个元素相同就不用考虑了
        //最后处于上升和下降状态下以i元素为结尾的湍流子数组的最大长度定义两个dp表
        //处于上升状态前面就要处于下降状态
        //处于下降状态前面就要处于上升状态
        int n = arr.size();
        vector<int> uparr(n, 1);
        vector<int> downarr(n, 1);
        int ret = 1;//至少为1
        for (int i = 1; i < n; i++)
        {
            if (arr[i] > arr[i - 1])
                uparr[i] = downarr[i - 1] + 1;

            else if (arr[i] < arr[i - 1])
                downarr[i] = uparr[i - 1] + 1;

            ret = max(ret, max(downarr[i], uparr[i]));
        }
        return ret;
    }
};
```
# 25. 单词拆分（medium）
https ://leetcode.cn/problems/word-break/submissions/575919570/
```cpp
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 以i位置结尾的子串和以j位置开头的单词能否加入到以0为起点，j-1为结尾的字符串中
        // 当然这个字符串是合法的
        // dp表值以i位置为结尾，0位置为开头的字符串能否被拼接而成
        // 状态转移方程为 dp[i] = dp[j-1]&&s.substr(j,i-1+1)在字典中
        int n = s.size();
        vector<int> dp(n + 1); // 不敢用vector<bool>
        // 我们用一个哈希表存储字典里的所有单词
        set<string> hash;
        for (auto& str : wordDict)
            hash.insert(str);
        dp[0] = true; // 添加一个虚拟节点，确保第一个单词能加入dp表中
        for (int i = 1; i < n + 1; i++)
        {
            for (int j = i; j > 0; j--)
            {
                dp[i] = dp[j - 1] && hash.find(s.substr(j - 1, i - j + 1)) != hash.end();
                if (dp[i])//如果找到一定要跳出，以leetcode为例当分成"leet""code"时不跳出j--，此时就区分成"lee""tcode"
                    break;//就会覆盖dp[i]了
            }
        }
        return dp[n];
    }
};
```